package org.example.myleet.stack;

import org.example.myleet.Utils.*;

import java.util.*;

public class StackSolution {

    /**
     * p42. 接雨水
     * 1 ms
     * 利用单调栈/动态规划，在O(n)的复杂度情况下获得某个位置左边或右边最高柱子
     */
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) {
            return 0;
        }
        //装水总和
        int sum = 0;
        //每一个位置其左边最高的近邻
        int[] leftHighestNeighbours = new int[n];
        //每一个位置其右边最高的近邻
        int[] rightHighestNeighbours = new int[n];
        //初始化为无效的位置
        Arrays.fill(leftHighestNeighbours, -1);
        Arrays.fill(rightHighestNeighbours, -1);
        int maxHeightIdx = -1;
        for (int i = 0; i < n; ++i) {
            //利用动态规划寻找某位置左边最高的近邻
            if (maxHeightIdx < 0 || height[i] >= height[maxHeightIdx]) {
                //如果当前位置更高，则刷新已经找到的左边的最高位置
                maxHeightIdx = i;
                continue;
            }
            leftHighestNeighbours[i] = maxHeightIdx;
        }
        //右侧如法炮制
        maxHeightIdx = -1;
        for (int i = n-1; i >= 0; --i) {
            if (maxHeightIdx < 0 || height[i] >= height[maxHeightIdx]) {
                maxHeightIdx = i;
                continue;
            }
            rightHighestNeighbours[i] = maxHeightIdx;
        }
        //最后根据每个位置的左右最高点求解每个位置的最大装水量，求和得结果
        for (int i = 0; i < n; ++i) {
            if (leftHighestNeighbours[i] > -1 && rightHighestNeighbours[i] > -1) {
                int minNeighbourHeight = Math.min(height[leftHighestNeighbours[i]], height[rightHighestNeighbours[i]]);
                int water = minNeighbourHeight - height[i];
                sum += water;
            }
        }
        return sum;
    }

    //71【栈】简化路径
    public String simplifyPath(String path) {
        //初始化栈，用于记录路径上文件夹的层次
        Deque<String> stack = new LinkedList<>();
        char[] charArr = path.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < charArr.length; ++i) {
            if (charArr[i] == '/') {
                //遇到'/'，说明到达一个目录，处理这个目录
                findDirectory(sb, stack);
            } else {
                //未遇到目录，拼接这个目录名称
                sb.append(charArr[i]);
            }
        }
        //最后一个目录名称要处理一下
        findDirectory(sb, stack);
        sb.delete(0, sb.length());
        //将stack中的文件夹拼接为路径
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop()).insert(0, '/');
        }
        if (sb.length() == 0) {
            //至少也要有'/'
            sb.append('/');
        }
        return sb.toString();
    }
    private void findDirectory(StringBuilder sb, Deque<String> stack) {
        if (sb.length() == 1) {
            if (sb.charAt(0) != '.') {
                //不是'.'，说明是文件夹名称，放到栈中缓存
                stack.push(sb.toString());
            }
            //是'.'，不需要处理
        } else if (sb.length() == 2) {
            if (sb.charAt(0) == '.' && sb.charAt(1) == '.') {
                //是'..'，代表返回上级目录，相当于栈顶退出
                if (!stack.isEmpty()) stack.pop();
            } else {
                //不是'..'，说明是文件夹名称，放到栈中缓存
                stack.push(sb.toString());
            }
        } else if (sb.length() > 2) {
            //是文件夹名称，放到栈中缓存
            stack.push(sb.toString());
        }
        //清理文件夹名称缓存
        sb.delete(0, sb.length());
    }

    /**
     * 84【栈】柱状图中最大的矩形
     * O(n)
     * 8 ms
     * 栈，寻找边界
     */
    public int largestRectangleArea(int[] heights) {
        //每一根柱子它自身最远可以延伸的左右边界
        int[] leftMargins = new int[heights.length];
        int[] rightMargins = new int[heights.length];
        for (int i=0;i<heights.length;i++) {
            //左右边界初始化
            leftMargins[i] = -1;
            rightMargins[i] = heights.length;
        }
        //利用栈的数据单调递增特性，维护一个可以寻找边界的单调递增数据结构
        Deque<int[]> stack = new LinkedList<>();
        for (int i=0;i<heights.length;i++) {
            //第i根柱子是观察柱子
            if (!stack.isEmpty()) {
                if (heights[i] > stack.peek()[0]) {
                    //1、观察柱子的高度比栈顶高，保持单调递增，更新观察柱子的左边界（因为单调递增，所以观察柱子的左边界就是栈顶）
                    leftMargins[i] = stack.peek()[1];
                } else {
                    while (!stack.isEmpty() && heights[i] <= stack.peek()[0]) {
                        //2、观察柱子的高度不高于栈顶，不能保持单调递增，更新栈顶柱子的右边界（因为不能保持单调递增，所以栈顶柱子的右边界就是观察柱子）
                        rightMargins[stack.peek()[1]] = i;
                        //不能保持单调递增，弹出栈顶，直到能够保持单调递增
                        stack.pop();
                    }
                    if (!stack.isEmpty()) {
                        //3、如果栈不是空的，更新观察柱子的左边界，此时符合单调递增，和第1点情况一致
                        leftMargins[i] = stack.peek()[1];
                    }
                }
            }
            //观察柱子入栈
            stack.push(new int[]{heights[i], i});
        }
        //最后如果栈里面还有柱子，需要逐个弹出并更新其左边界
        while (!stack.isEmpty()) {
            int[] height = stack.pop();
            if (!stack.isEmpty()) {
                leftMargins[height[1]] = stack.peek()[1];
            }
        }
        //遍历每一根柱子的左右边界计算面积，得到最大面结，x轴方向长度（长） = 右边界 - （左边界+1），高就是柱子的高度
        int maxSquare = 0;
        for (int i=0; i<heights.length; i++) {
            maxSquare = Math.max(maxSquare, (rightMargins[i] - leftMargins[i] - 1) * heights[i]);
        }
        return maxSquare;
    }

    /**
     * 85【栈】最大矩形
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int maxSquare = 0;
        int[] heights = new int[matrix[0].length];
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<heights.length; j++) {
                if (matrix[i][j] == '0') {
                    heights[j] = 0;
                } else {
                    heights[j] = heights[j] + 1;
                }
            }
            //每一根柱子它自身最远可以延伸的左右边界
            int[] leftMargins = new int[heights.length];
            int[] rightMargins = new int[heights.length];
            for (int i1 = 0; i1 < heights.length; i1++) {
                //左右边界初始化
                leftMargins[i1] = -1;
                rightMargins[i1] = heights.length;
            }
            //利用栈的数据单调递增特性，维护一个可以寻找边界的单调递增数据结构
            Deque<int[]> stack = new LinkedList<>();
            for (int i1 = 0; i1 < heights.length; i1++) {
                //第i根柱子是观察柱子
                if (!stack.isEmpty()) {
                    if (heights[i1] > stack.peek()[0]) {
                        //1、观察柱子的高度比栈顶高，保持单调递增，更新观察柱子的左边界（因为单调递增，所以观察柱子的左边界就是栈顶）
                        leftMargins[i1] = stack.peek()[1];
                    } else {
                        while (!stack.isEmpty() && heights[i1] <= stack.peek()[0]) {
                            //2、观察柱子的高度不高于栈顶，不能保持单调递增，更新栈顶柱子的右边界（因为不能保持单调递增，所以栈顶柱子的右边界就是观察柱子）
                            rightMargins[stack.peek()[1]] = i1;
                            //不能保持单调递增，弹出栈顶，直到能够保持单调递增
                            stack.pop();
                        }
                        if (!stack.isEmpty()) {
                            //3、如果栈不是空的，更新观察柱子的左边界，此时符合单调递增，和第1点情况一致
                            leftMargins[i1] = stack.peek()[1];
                        }
                    }
                }
                //观察柱子入栈
                stack.push(new int[]{heights[i1], i1});
            }
            //最后如果栈里面还有柱子，需要逐个弹出并更新其左边界
            while (!stack.isEmpty()) {
                int[] height = stack.pop();
                if (!stack.isEmpty()) {
                    leftMargins[height[1]] = stack.peek()[1];
                }
            }
            //遍历每一根柱子的左右边界计算面积，得到最大面结，x轴方向长度（长） = 右边界 - （左边界+1），高就是柱子的高度
            int maxSubResult = 0;
            for (int i1 = 0; i1 < heights.length; i1++) {
                maxSubResult = Math.max(maxSubResult, (rightMargins[i1] - leftMargins[i1] - 1) * heights[i1]);
            }
            maxSquare = Math.max(maxSquare, maxSubResult);
        }
        return maxSquare;
    }

    /**
     * 121【单调栈】买卖股票的最佳时机
     */
    public int maxProfit(int[] prices) {
        int answer = Integer.MIN_VALUE;
        int prevBottom = prices[0];
        for (int i = 0; i < prices.length; ++i) {
            if (prevBottom > prices[i]) {
                //如果prices[i]比prevBottom更小，此时弹出prevBottom，入栈prices[i]
                prevBottom = prices[i];
            }
            int profit = prices[i] - prevBottom;
            answer = Math.max(answer, profit);
        }
        return answer;
    }

    //p143
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean odd = false;
        while (fast != null) {
            fast = fast.next;
            if (null == fast) {
                odd = true;
                break;
            }
            fast = fast.next;
            slow = slow.next;
        }
        ListNode stop = slow;
        Deque<ListNode> queue = new LinkedList<>();
        ListNode cur = head;
        do {
            queue.push(cur);
            cur = cur.next;
        } while (cur != null && cur != stop);
        ListNode dummyHead = new ListNode(-1);
        if (odd) {
            dummyHead.next = cur;
        } else {
            ListNode prev = queue.pop();
            prev.next = cur;
            dummyHead.next = prev;
        }
        if (cur != null) {
            ListNode prev = cur;
            cur = cur.next;
            prev.next = null;
            while (cur != null) {
                prev = queue.pop();
                prev.next = cur;
                ListNode nNext = dummyHead.next;
                dummyHead.next = prev;
                cur = cur.next;
                prev.next.next = nNext;
            }
        }
        head = dummyHead.next;
    }

    /**
     * 144【栈-前序遍历】二叉树的前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        if (null == root) {
            return Collections.emptyList();
        }
        //迭代式前序遍历二叉树，顺序，根左右，先压入右节点再压入左节点，弹出顺序就是先左后右
        List<Integer> answer = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            answer.add(node.val);
            if (null != node.right) {
                stack.push(node.right);
            }
            if (null != node.left) {
                stack.push(node.left);
            }
        }
        return answer;
    }

    /**
     * 150【栈】逆波兰表达式求值
     * 8 ms
     * 逆波兰表达式最方便就是用栈进行计算
     */
    public int evalRPN(String[] tokens) {
        Deque<Long> stack = new LinkedList<>();
        int n = tokens.length;
        for (int i = 0; i < n; ++i) {
            char c = tokens[i].charAt(0);
            if (Character.isDigit(c) || tokens[i].length() > 1) {
                stack.push(Long.parseLong(tokens[i]));
            } else if (!stack.isEmpty()) {
                Long num1 = stack.pop();
                Long num2 = stack.pop();
                long newNum;
                if ('+' == c) {
                    newNum = num2 + num1;
                } else if ('-' == c) {
                    newNum = num2 - num1;
                } else if ('*' == c) {
                    newNum = num2 * num1;
                } else {
                    newNum = num2 / num1;
                }
                stack.push(newNum);
            }
        }
        return stack.peek().intValue();
    }


    /**
     * 173【栈】二叉搜索树迭代器
     */
    static class BSTIterator {

        private int i;

        private TreeNode[] stack;

        /**
         * 处理中节点
         * 优先入栈左节点直到左边再无下一层节点
         */
        private void processMid(TreeNode node) {
            while (node != null) {
                stack[i++] = node;
                node = node.left;
            }
        }

        /**
         * 24 ms
         * 栈迭代法做中序遍历。也可以用DFS。
         * 原则就是先弹出左子节点，然后看中节点如果还有右节点，就将右节点重新当作中节点处理
         */
        public BSTIterator(TreeNode root) {
            TreeNode node = root;
            i = 0;
            stack = new TreeNode[10000];
            //需要优先入栈左节点直到左边再无下一层节点，此时栈顶的节点即为二叉搜索树最小的值
            //此操作完成后能够保证栈内的节点都是左子节点优先的，后续next的时候只要关注右节点即可
            processMid(node);
        }

        public int next() {
            //取出栈顶节点返回其值
            TreeNode node = stack[--i];
            if (node.right == null) {
                //如果栈顶节点没有右子节点，说明是叶子节点，没有其他操作
                return node.val;
            }
            //非叶子节点时，说明此节点原来是中节点，返回其值，并将右节点作为中节点处理，入栈其所有左子节点
            int retValue = node.val;
            node = node.right;
            processMid(node);
            return retValue;
        }

        public boolean hasNext() {
            //栈不为空就还未遍历完
            return i > 0;
        }
    }

    /**
     * 224【栈】基本计算器
     * 28 ms
     */
    static class FormulaObject {
        public static final int OPERAND = 0;
        public static final int BRACKET = 1;
        public static final int NUMBER = 2;
        int type;
        long value;
        String raw;

        public FormulaObject(int type, String raw) {
            this.type = type;
            this.raw = raw;
        }

        public FormulaObject(int type, long value, String raw) {
            this.type = type;
            this.value = value;
            this.raw = raw;
        }

        @Override
        public String toString() {
            return raw;
        }
    }
    public int calculate224(String s) {
        final int PLUS = 1;
        final int MINUS = 2;
        Deque<FormulaObject> stack = new LinkedList<>();
        int n = s.length(), i = 0;
        while (i < n) {
            char c = s.charAt(i);
            if ('(' == c) {
                FormulaObject o = new FormulaObject(FormulaObject.BRACKET, "(");
                stack.push(o);
                ++i;
            } else if (Character.isDigit(c)) {
                long num = 0;
                while (Character.isDigit(c)) {
                    num = 10 * num + (c - 48);
                    ++i;
                    if (i < n) {
                        c = s.charAt(i);
                    } else {
                        break;
                    }
                }
                FormulaObject o = new FormulaObject(FormulaObject.NUMBER, num, num + "");
                stack.push(o);
            } else if ('+' == c || '-' == c) {
                int operandType = '+' == c ? PLUS : MINUS;
                ++i;
                while (' ' == s.charAt(i)) {
                    ++i;
                }
                c = s.charAt(i);
                if (Character.isDigit(c)) {
                    if (stack.isEmpty()) {
                        FormulaObject zero = new FormulaObject(FormulaObject.NUMBER, 0L, "0");
                        stack.push(zero);
                    }
                    //操作符号下一个是数字，先计算完再入栈
                    long num = 0;
                    while (Character.isDigit(c)) {
                        num = 10 * num + (c - 48);
                        ++i;
                        if (i < n) {
                            c = s.charAt(i);
                        } else {
                            break;
                        }
                    }
                    long v;
                    if (PLUS == operandType) {
                        v = stack.pop().value + num;
                    } else {
                        v = stack.pop().value - num;
                    }
                    FormulaObject o = new FormulaObject(FormulaObject.NUMBER, v, num + "");
                    stack.push(o);
                } else {
                    //否则就一定是左括号，需要将操作符号和左括号入栈
                    FormulaObject o2 = new FormulaObject(FormulaObject.OPERAND, PLUS == operandType ? "+" : "-");
                    stack.push(o2);
                    FormulaObject o1 = new FormulaObject(FormulaObject.BRACKET, new String(new char[]{c}));
                    stack.push(o1);
                    ++i;
                }
            } else if (')' == c) {
                //遇到右括号就弹出最近的数字，并将对应的左括号弹出
                FormulaObject o = stack.pop();
                if ((!stack.isEmpty()) && FormulaObject.BRACKET == stack.peek().type && '(' == stack.peek().raw.charAt(0)) stack.pop();
                //检查栈顶的是不是符号，如果是符号则弹出相应的数字进行计算
                while ((!stack.isEmpty()) && FormulaObject.OPERAND == stack.peek().type) {
                    int operandType = '+' == stack.pop().raw.charAt(0) ? PLUS : MINUS;
                    if (stack.isEmpty()) {
                        FormulaObject zero = new FormulaObject(FormulaObject.NUMBER, 0L, "0");
                        stack.push(zero);
                    }
                    long v;
                    if (PLUS == operandType) {
                        v = stack.pop().value + o.value;
                    } else {
                        v = stack.pop().value - o.value;
                    }
                    o = new FormulaObject(FormulaObject.NUMBER, v, v + "");
                }
                stack.push(o);
                ++i;
            } else {
                ++i;
            }
        }
        return (int) stack.peek().value;
    }

    /**
     * 227【栈】基本计算器 II
     * 48 ms
     */
    public int calculate227(String s) {
        Deque<FormulaObject> stack = new LinkedList<>();
        int n = s.length(), i = 0;
        while (i<n) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                //遇到数字就读取整个数字并入栈
                long num = 0;
                while (Character.isDigit(c)) {
                    num = 10 * num + (c - 48);
                    ++i;
                    if (i < n) {
                        c = s.charAt(i);
                    } else {
                        break;
                    }
                }
                if (!stack.isEmpty()) {
                    char operand = stack.peek().raw.charAt(0);
                    if ('*' == operand || '/' == operand) {
                        //乘法或除法需要先执行运算
                        stack.pop();
                        FormulaObject numberObject = stack.pop();
                        if ('*' == operand) {
                            num = numberObject.value * num;
                        } else {
                            num = numberObject.value / num;
                        }
                    } else if ('-' == operand) {
                        //减法时，减号代表负数，非第一个数时需要补充加号
                        stack.pop();
                        num = -num;
                        if (!stack.isEmpty()) {
                            FormulaObject o = new FormulaObject(FormulaObject.OPERAND, "+");
                            stack.push(o);
                        }
                    }
                }
                FormulaObject number = new FormulaObject(FormulaObject.NUMBER, num, num + "");
                stack.push(number);
            } else if ('+' == c || '-' == c || '*' == c || '/' == c) {
                FormulaObject o = new FormulaObject(FormulaObject.OPERAND, new String(new char[]{c}));
                stack.push(o);
                ++i;
            } else {
                //空格没有意义直接跳过
                ++i;
            }
        }
        while (stack.size() > 1) {
            FormulaObject numberObject1 = stack.pop();
            char operand = stack.pop().raw.charAt(0);
            FormulaObject numberObject2 = stack.pop();
            long num;
            if ('+' == operand) {
                num = numberObject2.value + numberObject1.value;
            } else {
                num = numberObject2.value - numberObject1.value;
            }
            FormulaObject number = new FormulaObject(FormulaObject.NUMBER, num, "" + num);
            stack.push(number);
        }
        return (int) stack.peek().value;
    }

    /**
     * 232【双栈】用栈实现队列
     */
    static class MyQueue {

        private Stack<Integer> in;
        private Stack<Integer> out;

        /**
         * 0 ms
         * 双栈，一个栈用来接收入队的数据，另一个栈用来出队，当需要peak或pop的时候，入队的栈将数据倒入出队栈中，顺序自然就按照先进先出的顺序了
         */
        /** Initialize your data structure here. */
        public MyQueue() {
            in = new Stack<>();
            out = new Stack<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            in.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if (out.isEmpty()) {
                pour();
            }
            return out.pop();
        }

        /** Get the front element. */
        public int peek() {
            if (out.isEmpty()) {
                pour();
            }
            return out.peek();
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            if (out.isEmpty()) {
                pour();
                return out.isEmpty();
            }
            return false;
        }

        private void pour() {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    /**
     * 234【栈】回文链表
     * 自创解法，1ms，41MB内存消耗
     */
    public boolean isPalindrome(ListNode head) {
        if (null == head) {
            //这里是第一个坑，空链表也属于回文，回文定义是左边读和右边读过来是一样的
            return true;
        }
        ListNode cur = head;
        //先统计单向链表的长度
        int len = 0;
        while (null != cur) {
            ++len;
            cur = cur.next;
        }
        if (1 == len) {
            //只有1长度的链表当然属于回文
            return true;
        }
        //单数和双数区别对待
        boolean even = len % 2 == 0;
        //双数时，开始检查回文点位于二分之一长度的下一个；单数时，开始检查回文点位于中间点的下一个
        int backPoint = even ? len / 2 + 1 : len / 2 + 2;
        //用于存放检查的字符
        int[] stack = new int[len+1];
        cur = head;
        int i = 1;
        //再从后半段开始检查是否回文
        while (null != cur) {
            if (i < backPoint) {
                if (!even && i == backPoint - 1) {
                    //单数情况，中间点位置，跳过检查，检查点往左回一位，下一回合将开始检查回文
                    --backPoint;
                    cur = cur.next;
                    ++i;
                    continue;
                }
                //小于二分之一长度时，记录链表的值
                stack[i] = cur.val;
            } else {
                //已经越过检查点位置，开始检查回文，往左移动一位，检查是否匹配回文
                --backPoint;
                if (stack[backPoint] != cur.val) {
                    return false;
                }
            }
            cur = cur.next;
            ++i;
        }
        return true;
    }

    /**
     * 239【单调栈】滑动窗口最大值
     * 36 ms
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        //init
        //双端队列，可以同时弹出队首和队尾的元素，按nums[i]单调递减的方式保存nums的下标i
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        int[] result = new int[nums.length - k + 1];
        result[0] = nums[queue.peekFirst()];
        //slide
        for (int i = k; i < nums.length; i++) {
            //窗口滑动时，先移除窗口最左边的元素，再加入窗口右边进来的新元素
            if (!queue.isEmpty() && i - k == queue.peekFirst()) {
                //如果需要移除的元素的位置是当前的最大值，只好移除掉，否则不用移除也可以，因为后面轮不到这个更小的数登场
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                //比较队列尾部的元素，一直弹出直至新加入的元素符合递减规律，保持队列单调递减的特性
                queue.pollLast();
            }
            queue.offerLast(i);
            //这时平均下来只要用O(1)的时间即可找到每次滑动窗口后的队列头部的最大值，即窗口中的最大值
            result[i - k + 1] = nums[queue.peekFirst()];
        }
        return result;
    }

    /**
     * 316【栈】去除重复字母
     * 利用栈的特性构造字典序递增的字符串，这里要注意的是如果某个字母只剩1个，则不能再弹出，因为要保持字母相对位置不变
     */
    public String removeDuplicateLetters(String s) {
        if (s.length() == 1) {
            return s;
        }
        //1、统计字母的频次
        short[] count = new short[128];
        for (int i = 0; i < s.length(); i++) {
            ++count[s.charAt(i)];
        }
        //2、利用栈构建出字典序最小的结果
        Deque<Character> stack = new LinkedList<>();
        boolean[] characterAdded = new boolean[128];
        char[] sCharArr = s.toCharArray();
        for (char c : sCharArr) {
            //当前观察的字母c
            if (stack.isEmpty()) {
                stack.push(c);
                characterAdded[c] = true;
            } else {
                char p = stack.peek();
                if (p == c || characterAdded[c]) {
                    //情况1，如果栈中已经存在c，说明c已经在合适的位置，无需再追加，频数-1
                    --count[c];
                } else if (p < c) {
                    //情况2，字典序递增，可以直接追加
                    stack.push(c);
                    characterAdded[c] = true;
                } else {
                    //情况3，字典序递增被破坏，此时需要适当处理栈中的值来重新获得合适的字典序
                    if (count[p] >= 2) {
                        //如果栈顶的字母只有1个，那么就不能剔除之，直接在这个字母后面追加
                        while ((!stack.isEmpty())) {
                            p = stack.peek();
                            if (c > p || count[p] < 2) {
                                //符合字典序递增，或者p的频数剩1，不能再剔除，跳出
                                break;
                            }
                            //存在p，p的频数>1，因此可以将p剔除，等后面再追加
                            p = stack.pop();
                            characterAdded[p] = false;
                            --count[p];
                        }
                    }
                    //追加字母c
                    stack.push(c);
                    characterAdded[c] = true;
                }
            }
        }
        //3、导出结果
        char[] result = new char[stack.size()];
        int idx = stack.size() - 1;
        while (!stack.isEmpty()) {
            result[idx--] = stack.pop();
        }
        return new String(result);
    }

    /**
     * 331【栈】验证二叉树的前序序列化
     * 10 ms
     */
    public boolean isValidSerialization(String preorder) {
        if (preorder.length() == 0) {
            return true;
        }
        if (preorder.charAt(preorder.length()-1) != '#') {
            return false;
        }
        Deque<String> stack = new LinkedList<>();
        int s = 0, e = s, n = preorder.length();
        while (s < n) {
            if (stack.size() == 1 && stack.peek().charAt(0) == '#') {
                return false;
            }
            if (stack.size() > 2) {
                String s1 = stack.pop();
                String s2 = stack.pop();
                if (s1.charAt(0) == '#' && s2.charAt(0) == '#') {
                    stack.pop();
                    stack.push("#");
                    continue;
                } else {
                    stack.push(s2);
                    stack.push(s1);
                }
            }
            while (e < n && preorder.charAt(e) != ',') {
                ++e;
            }
            stack.push(preorder.substring(s, e));
            s = e + 1;
            e = s;
        }
        while (stack.size() > 2) {
            String s1 = stack.pop();
            String s2 = stack.pop();
            if (s1.charAt(0) == '#' && s2.charAt(0) == '#') {
                stack.pop();
                stack.push("#");
            } else {
                break;
            }
        }
        return stack.isEmpty() || (stack.size() == 1 && stack.peek().charAt(0) == '#');
    }

    /**
     * 341【栈】扁平化嵌套列表迭代器
     * 4 ms
     * 利用栈展开嵌套列表，最坑的是空列表的情况
     */
    interface NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        List<NestedInteger> getList();
    }
    static class NestedIterator implements Iterator<Integer> {
        private Deque<NestedInteger> stack = new LinkedList<>();
        public NestedIterator(List<NestedInteger> nestedList) {
            pushToStack(nestedList);
        }
        @Override
        public Integer next() {
            //按顺序推出就可以遵循原来的顺序
            return stack.pop().getInteger();
        }
        @Override
        public boolean hasNext() {
            NestedInteger item;
            while (!stack.isEmpty() && !(item = stack.peek()).isInteger()) {
                //当栈顶元素不是数字而是列表时，将列表各个元素从后往前推到栈中
                stack.pop();
                List<NestedInteger> items = item.getList();
                pushToStack(items);
            }
            return !stack.isEmpty();
        }
        /**
         * 将列表元素按照列表从后往前推到栈中，使得栈推出时能够遵循原来的顺序
         */
        private void pushToStack(List<NestedInteger> items) {
            int n = items.size();
            for (int i=n-1; i>=0; --i) {
                stack.push(items.get(i));
            }
        }
    }

    /**
     * 381【哈希表+栈】O(1) 时间插入、删除和获取随机元素 - 允许重复
     */
    class RandomizedCollection {

        //数值集合
        private List<Integer> values;

        //数值元素出现的位置
        private Map<Integer, Deque<Integer>> valuePositionMap;

        /** Initialize your data structure here. */
        public RandomizedCollection() {
            values = new ArrayList<>();
            valuePositionMap = new HashMap<>();
        }

        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            int valPosition = values.size();
            values.add(val);
            Deque<Integer> positions = valuePositionMap.get(val);
            boolean contain = positions != null;
            if (null == positions) positions = new LinkedList<>();
            positions.push(valPosition);
            valuePositionMap.put(val, positions);
            return !contain;
        }

        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            Deque<Integer> positions = valuePositionMap.get(val);
            if (null == positions) return false;
            Integer valPosition = positions.pop();
            if (valPosition < (values.size() - 1)) {
                //如果要移除的数不是最后一位，这里可以做一个巧妙的转换
                //将最后一位和要移除的位置的数值调换（当然也要修正被调换数的位置缓存，并按增序排好），然后直接移除最后一位就行了
                Integer lastValue = values.get(values.size() - 1);
                Deque<Integer> lastValuePositions = valuePositionMap.get(lastValue);
                //移除最后一个值的位置，用valPosition代替，并将栈中元素逐个弹出，插入valPosition之后再重新压入，以整理成严格单调递增
                lastValuePositions.pop();
                Deque<Integer> lastValuePosTemp = new LinkedList<>();
                while (!lastValuePositions.isEmpty() && lastValuePositions.peek() > valPosition) {
                    lastValuePosTemp.push(lastValuePositions.pop());
                }
                lastValuePositions.push(valPosition);
                while (!lastValuePosTemp.isEmpty()) {
                    lastValuePositions.push(lastValuePosTemp.pop());
                }
                valuePositionMap.put(lastValue, lastValuePositions);
                //位置已经整理完成，valPosition放入values的最后一个值，完成替换
                values.set(valPosition, lastValue);
            }
            if (positions.isEmpty()) {
                //如果val值的位置被全部移除，则移除位置缓存
                valuePositionMap.remove(val);
            }
            values.remove(values.size() - 1);
            return true;
        }

        /** Get a random element from the collection. */
        public int getRandom() {
            if (0 == values.size()) {
                return -1;
            }
            return values.get((int) (Math.random() * values.size()));
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("RandomizedCollection{");
            sb.append("values=").append(values);
            sb.append('}');
            return sb.toString();
        }
    }

    /**
     * 449【栈】序列化和反序列化二叉搜索树
     */
    static class Codec {

        private static final char NULL = 'n';
        private static final char SEPARATOR = ',';

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (null == root) {
                return "";
            }
            StringBuilder sb = new StringBuilder();
            Deque<TreeNode> deque = new LinkedList<>();
            deque.offer(root);
            while (!deque.isEmpty()) {
                int size = deque.size();
                for (int i = 0; i < size; ++i) {
                    TreeNode node = deque.poll();
                    if (null == node) {
                        sb.append(NULL);
                    } else {
                        sb.append(node.val);
                        deque.offer(node.left);
                        deque.offer(node.right);
                    }
                    sb.append(SEPARATOR);
                }
            }
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.length() < 1) {
                return null;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            char[] charArr = data.toCharArray();
            int i = 0;
            while (charArr[i] != SEPARATOR) {
                sb.append(charArr[i++]);
            }
            TreeNode root = new TreeNode(Integer.parseInt(sb.toString()));
            deque.offer(root);
            sb = new StringBuilder();
            ++i;
            while (!deque.isEmpty() && i < charArr.length) {
                TreeNode node = deque.poll();
                while (charArr[i] != SEPARATOR) {
                    sb.append(charArr[i++]);
                }
                if (sb.charAt(0) != NULL) {
                    node.left = new TreeNode(Integer.parseInt(sb.toString()));
                    deque.offer(node.left);
                }
                sb = new StringBuilder();
                ++i;
                while (charArr[i] != SEPARATOR) {
                    sb.append(charArr[i++]);
                }
                if (sb.charAt(0) != NULL) {
                    node.right = new TreeNode(Integer.parseInt(sb.toString()));
                    deque.offer(node.right);
                }
                sb = new StringBuilder();
                ++i;
            }
            return root;
        }
    }

    //p895
    static class FreqStack0 {

        private Deque<Integer> stack;

        private Map<Integer, Integer> valDelCntMap;

        private Map<Integer, Integer> valCntMap;

        private TreeMap<Integer, Set<Integer>> cntValSetTreeMap;

        public FreqStack0() {
            stack = new LinkedList<>();
            valDelCntMap = new HashMap<>();
            valCntMap = new HashMap<>();
            cntValSetTreeMap = new TreeMap<>(Comparator.naturalOrder());
        }

        public void push(int val) {
            stack.push(val);
            int cnt =  valCntMap.getOrDefault(val, 0);
            int newCnt = cnt + 1;
            valCntMap.put(val, newCnt);
            if (cnt > 0) {
                cntValSetTreeMap.get(cnt).remove(val);
            }
            Set<Integer> valSet = cntValSetTreeMap.getOrDefault(newCnt, new HashSet<>());
            valSet.add(val);
            cntValSetTreeMap.put(newCnt, valSet);
        }

        public int pop() {
            Integer val = stack.peek();
            int delCnt = valDelCntMap.getOrDefault(val, 0);
            while (delCnt > 0 && val != null) {
                stack.pop();
                val = stack.peek();
                delCnt = valDelCntMap.getOrDefault(val, 0);
            }
            Map.Entry<Integer, Set<Integer>> maxFreqEntry = cntValSetTreeMap.lastEntry();
            int cnt = maxFreqEntry.getKey();
            Set<Integer> valSet = maxFreqEntry.getValue();
            if (valSet.contains(val)) {
                stack.pop();
                valSet.remove(val);
                if (valSet.isEmpty()) {
                    cntValSetTreeMap.remove(cnt);
                }
                int newCnt = cnt - 1;
                if (newCnt > 0) {
                    Set<Integer> newValSet = cntValSetTreeMap.getOrDefault(newCnt, new HashSet<>());
                    newValSet.add(val);
                    cntValSetTreeMap.put(newCnt, newValSet);
                }
                valCntMap.put(val, newCnt);
            } else {
                Deque<Integer> tempStack = new LinkedList<>();
                while (!stack.isEmpty()) {
                    val = stack.pop();
                    if (valSet.contains(val)) {
                        valSet.remove(val);
                        if (valSet.isEmpty()) {
                            cntValSetTreeMap.remove(cnt);
                        }
                        int newCnt = cnt - 1;
                        if (newCnt > 0) {
                            Set<Integer> newValSet = cntValSetTreeMap.getOrDefault(newCnt, new HashSet<>());
                            newValSet.add(val);
                            cntValSetTreeMap.put(newCnt, newValSet);
                        }
                        valCntMap.put(val, newCnt);
                        break;
                    } else {
                        tempStack.push(val);
                    }
                }
                while (!tempStack.isEmpty()) {
                    stack.push(tempStack.pop());
                }
            }
            return val;
        }
    }

    static class FreqStack {

        private Map<Integer, Deque<Integer>> stacks;

        private Map<Integer, Integer> valCntMap;

        private int maxCount;

        public FreqStack() {
            valCntMap = new HashMap<>();
            stacks = new HashMap<>();
            maxCount = 0;
        }

        public void push(int val) {
            int cnt =  valCntMap.getOrDefault(val, 0);
            int newCnt = cnt + 1;
            valCntMap.put(val, newCnt);
            Deque<Integer> stack = stacks.getOrDefault(newCnt, new LinkedList<>());
            stack.push(val);
            stacks.put(newCnt, stack);
            maxCount = Math.max(maxCount, newCnt);
        }

        public int pop() {
            int val = stacks.get(maxCount).pop();
            valCntMap.put(val, valCntMap.get(val) - 1);
            if (stacks.get(maxCount).isEmpty()) {
                --maxCount;
            }
            return val;
        }
    }

    /**
     * 901【单调栈】股票价格跨度
     * 题目要求知道低于当前price的连续个数，也就是通过单调递减的序列找到恰好比当前price大的最新序号
     */
    class StockSpanner {
        //单调栈，int[]记录的是价格和序号，按单调递减存放
        private final Deque<int[]> stack;
        //序号，一直累加
        private int serial;

        public StockSpanner() {
            stack = new LinkedList<>();
            serial = 0;
        }

        public int next(int price) {
            //每次调用next就累加
            ++serial;
            //前一个大于当前price的价格的序号
            int prevSerial = 0;
            //维护单调栈，将小于等于当前price的价格都去掉，保持单调递减
            while (!stack.isEmpty() && stack.peek()[0] <= price) {
                stack.pop();
            }
            //如果单调栈空了，说明前面没有更小的价格的序号了；如果不是空的，栈顶的序号对应的价格就是恰好比当前序号的price大的
            //因此通过serial - prevSerial就可以得到当前next的答案
            if (!stack.isEmpty()) {
                prevSerial = stack.peek()[1];
            }
            //当前的price及其序号入栈
            stack.push(new int[]{price, serial});
            return serial - prevSerial;
        }
    }

    /**
     * 907【单调栈+动态规划】子数组的最小值之和
     * 考察[3,1,2,4]这个数组，我们考察以第i个数字为结尾的子数组，考察顺序就是
     * [3]
     * [3,1]，[1]
     * [3,1,2]，[1,2]，[2]
     * [3,1,2,4]，[1,2,4]，[2,4]，[4]
     * 可以知道第i行的子数组个数是i+1（i从0开始），以上就是一个数组的所有子数组的拆解
     * 当将第i个数加到第i-1种情况时产生的结果有2种
     * 1、一种是新加入的第i个数最大，那么此情况下只有以arr[i]结尾的子数组的最小值都是arr[i]
     * 2、另一种是新加入的arr[i]比dp[i-1]对应的子数组中已知的最小值值更小，则先找到数组中比arr[i]大的数，将他们的贡献min(b)次数先求出，由于这些贡献次数被更小的arr[i]，因此要先用dp[i-1]减去这些更大的数的贡献值，然后再求arr[i]的贡献次数
     * 要很方便地知道一个排列中所有比arr[i]大的数，可以用单调栈维护，栈顶的数字最大
     * i=0，入栈3，栈顶[3]，3贡献了1次，dp[0]=3
     * i=1，弹出3，入栈1，栈顶[1]，所以知道3在dp[i-1]中贡献了1次，1贡献了2次，dp[1]=dp[0]-1*3+2*1=2
     * i=2，入栈2，栈顶[2,1]，因没有弹出，所以2只贡献了最后一个子数组[2]，dp[2]=dp[1]+1*2=4
     * i=2，入栈4，栈顶[4,2,1]，因没有弹出，所以4只贡献了最后一个子数组[4]，dp[3]=dp[2]+1*4=8
     * 知道每一行的结果，最后只需sum(dp[i])0→i-1，就可以得到总的结果。3+2+4+8=17
     */
    public int sumSubarrayMins(int[] arr) {
        final int MOD = 1000000007;
        int n = arr.length;
        //记录从0~n-1数字选择时对应的总和
        int[] dp = new int[n];
        //记录单调递增的数字及其对当前状态的贡献次数，Stack<{数字，贡献次数}>
        Deque<int[]> stack = new LinkedList<>();
        //第一个数字选择时不难想到总和就是arr[0]，并且贡献了1次
        dp[0] = arr[0];
        stack.push(new int[]{arr[0], 1});
        for (int i = 1; i < n; ++i) {
            //popCount-弹出的数字总共的贡献次数，popSum-弹出的数字总共的贡献值
            int popCount = 0, popSum = 0;
            while (!stack.isEmpty() && arr[i] <= stack.peek()[0]) {
                //保持栈中单调递增，被弹出的数字的贡献次数及其贡献值需要记录下来
                popCount += stack.peek()[1];
                popSum += ((long) stack.peek()[0] * (long) stack.peek()[1] % MOD);
                popSum %= MOD;
                stack.pop();
            }
            //新值arr[i]的贡献次数
            int newElementCount = popCount + 1;
            //新值arr[i]的贡献值
            int newElementAttribution = (int) ((long) newElementCount * (long) arr[i] % MOD);
            //dp[i] = dp[i - 1] - 被弹出的数字的贡献值 + 新值arr[i]的贡献值
            dp[i] = dp[i - 1] - popSum + newElementAttribution;
            dp[i] %= MOD;
            stack.push(new int[]{arr[i], newElementCount});
        }
        //结果就是把dp求和
        int answer = 0;
        for (int s : dp) {
            answer += s;
            answer %= MOD;
        }
        return answer;
    }

    //p1019
    public int[] nextLargerNodes(ListNode head) {
        int n = 1;
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
            ++n;
        }
        int[] answer = new int[n];
        Deque<int[]> idxValuePairStack = new LinkedList<>();
        int i = 0;
        cur = head;
        idxValuePairStack.push(new int[]{i, cur.val});
        while (cur.next != null) {
            cur = cur.next;
            ++i;
            if (null != idxValuePairStack.peek() && cur.val > idxValuePairStack.peek()[1]) {
                int[] pair = idxValuePairStack.peek();
                do {
                    answer[pair[0]] = cur.val;
                    idxValuePairStack.pop();
                    if (idxValuePairStack.isEmpty()) break;
                    pair = idxValuePairStack.peek();
                } while (cur.val > pair[1]);
            }
            idxValuePairStack.push(new int[]{i, cur.val});
        }
        return answer;
    }

    //p1106
    private static final int NOT = 1;
    private static final int OR = 2;
    private static final int AND = 3;
    private static final int TRUE = 4;
    private static final int FALSE = 5;

    public boolean parseBoolExpr(String expression) {
        int n = expression.length();
        int size = 0;
        int[] stack = new int[n];
        int i = 0;
        while (i < n) {
            char c = expression.charAt(i);
            if (c == '!') {
                stack[size++] = NOT;
                ++i;
            } else if (c == '|') {
                stack[size++] = OR;
                ++i;
            } else if (c == '&') {
                stack[size++] = AND;
                ++i;
            } else if (c == ')') {
                //找到一个能够归并的结果范围，弹出对应的操作符号，计算操作符范围内的归并结果
                List<Integer> booleans = new ArrayList<>();
                int operand = stack[--size];
                while (operand > 3) {
                    booleans.add(operand);
                    operand = stack[--size];
                }
                int result = booleans.get(0);
                if (operand == NOT) {
                    if (result == TRUE) {
                        result = FALSE;
                    } else {
                        result = TRUE;
                    }
                } else if (operand == OR) {
                    for (int j = 1; j < booleans.size(); ++j) {
                        if (booleans.get(j) == TRUE) {
                            result = TRUE;
                            break;
                        }
                    }
                } else {
                    for (int j = 1; j < booleans.size(); ++j) {
                        if (booleans.get(j) == FALSE) {
                            result = FALSE;
                            break;
                        }
                    }
                }
                stack[size++] = result;
            } else if (c == 't') {
                stack[size++] = TRUE;
            } else if (c == 'f') {
                stack[size++] = FALSE;
            }
            ++i;
        }
        return stack[0] == TRUE;
    }

    //p1996
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    //战力相同时按防御升序排序
                    return o2[1] - o1[1];
                }
                //按战力升序排序
                return o1[0] - o2[0];
            }
        });
        int n = properties.length;
        int size = 0;
        int[][] stack = new int[n][2];
        int weakCharacterCount = 0;
        stack[size++] = properties[0];
        for (int i = 1; i < n; ++i) {
            //由于战力一定是非递减，因此character的战力一定比之前出现过的character战力更高，至少相同
            //因此栈顶的character的防御值一定更弱
            //因此接下来判断防御力是否也更大就可以判断栈中的角色是不是弱角色
            int[] character = properties[i];
            while (size > 0 && character[0] > stack[size - 1][0] && character[1] > stack[size - 1][1]) {
                //遇到弱角色，出栈并记录
                --size;
                ++weakCharacterCount;
            }
            //栈空了或栈底角色暂时还不是弱角色，本轮character入栈
            stack[size++] = character;
        }
        return weakCharacterCount;
    }

    /**
     * 2116【贪心+栈】判断一个括号字符串是否有效
     * 参考：https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/solutions/1179134/pan-duan-yi-ge-gua-hao-zi-fu-chuan-shi-f-0s47/comments/2992150/?parent=2991748
     * 1.长度是奇数返回假。
     * 2.从左到右扫描，尽量都改成左括号，一旦有多余的右括号返回假。
     * 3.从右到左扫描，尽量都改成右括号，一旦有多余的左括号返回假。
     * 4.返回真。
     */
    public boolean canBeValid(String s, String locked) {
        if (s.length() % 2 != 0) return false;
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if ('0' == locked.charAt(i)) {
                if (')' == c) {
                    c = '(';
                }
            }
            if (!stack.isEmpty() && ')' == c && '(' == stack.peek()) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) {
            if (')' == stack.pop()) return false;
        }
        for (int i = s.length() - 1; i >= 0; --i) {
            char c = s.charAt(i);
            if ('0' == locked.charAt(i)) {
                if ('(' == c) {
                    c = ')';
                }
            }
            if (!stack.isEmpty() && '(' == c && ')' == stack.peek()) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) {
            if ('(' == stack.pop()) return false;
        }
        return true;
    }

    /**
     * 2512【哈希表+优先堆】奖励最顶尖的 K 名学生
     */
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        int n = student_id.length;
        Set<Integer> positiveWords = new HashSet<>(positive_feedback.length);
        for (String word : positive_feedback) {
            positiveWords.add(word.hashCode());
        }
        Set<Integer> negativeWords = new HashSet<>(negative_feedback.length);
        for (String word : negative_feedback) {
            negativeWords.add(word.hashCode());
        }
        PriorityQueue<int[]> studentScores = new PriorityQueue<>(n, (a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });
        for (int i = 0; i < n; ++i) {
            String[] words = report[i].split(" ");
            int score = 0;
            for (String word : words) {
                if (positiveWords.contains(word.hashCode())) {
                    score += 3;
                } else if (negativeWords.contains(word.hashCode())) {
                    score -= 1;
                }
            }
            studentScores.offer(new int[]{student_id[i], score});
        }
        List<Integer> answer = new ArrayList<>(k);
        for (int i = 0; i < k; ++i) {
            answer.add(studentScores.poll()[0]);
        }
        return answer;
    }

    /**
     * 2865【单调栈】美丽塔 I
     * 思路：从题目的意思可以知道我们要针对每个i，利用maxHeights[i]作为最大值，构造一个n元素山脉数组，然后对山脉数组求和，找到最大和
     * 朴素做法如下
     *     public long maximumSumOfHeights(List<Integer> maxHeights) {
     *         long answer = 0L, n = maxHeights.size();
     *         for (int i = 0; i < n; ++i) {
     *             //下面利用maxHeights[i]构造山脉数组，并求和cur
     *             int prevL = maxHeights.get(i), prevR = prevL, l = i - 1, r = i + 1;
     *             long cur = prevL;
     *             while (l >= 0) {
     *                 int h = maxHeights.get(l);
     *                 if (h <= prevL) {
     *                     cur += h;
     *                     prevL = h;
     *                 } else {
     *                     cur += prevL;
     *                 }
     *                 --l;
     *             }
     *             while (r < n) {
     *                 int h = maxHeights.get(r);
     *                 if (h <= prevR) {
     *                     cur += h;
     *                     prevR = h;
     *                 } else {
     *                     cur += prevR;
     *                 }
     *                 ++r;
     *             }
     *             answer = Math.max(answer, cur);
     *         }
     *         return answer;
     *     }
     * 朴素做法的时间复杂度为O(n^2)
     * 参考了一些解法，思考明白了其实有很多回退是不必要，举例[5,3,4,1,1]，逐个数观察，
     * 当i=0，山脉数组左侧为[5]
     * 当i=1，山脉数组左侧为[3,3] //遇到比较小的数，则左边所有大于maxHeights[i]的值全部变成maxHeights[i]
     * 当i=2，山脉数组左侧为[3,3,4] //遇到不小于maxHeights[i-1]更大的数，此时i=1的情况不变，只是把maxHeights[i]加上去就行
     * 当i=3，山脉数组左侧为[1,1,1,1] //遇到比较小的数，则左边所有大于maxHeights[i]的值全部变成maxHeights[i]
     * 当i=4，山脉数组左侧为[1,1,1,1,1] //遇到不小于maxHeights[i-1]更大的数，此时i=1的情况不变，只是把maxHeights[i]加上去就行
     * 把x个值变成maxHeights[i]，这一个步骤可以用一个长度为2的数组记录[maxHeights[i], x]
     * 而每次遇到比较小的数都要进行变值处理，也就是一种非递增的情况，考虑用单调栈辅助实现操作和记录
     * 小结操作方法：
     * 1、单调栈初始化时用一个0垫底
     * 2、单调栈中保持栈顶的数要不大于准备入栈的数，大于准备入栈的数都需要从栈中弹出，并且这些弹出的数字都需要变成准备入栈的数
     * 3、准备入栈的数字记录好总共有多少个
     * 4、利用准备入栈的数字num和个数x求得num * x的结果，而pre[i + 1 - x]之前的值由于没有弹出过变更过，因此可以直接得到
     * 5、重复步骤1~4，完成所有i位置形成山脉数组时的最优和（O(n)）
     * 6、如法炮制山脉数组的右侧（O(n)）
     * 7、将两侧的最优和合并在一起找到最大和（O(n)）
     * 因此总的时间复杂度是O(n)
     */
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        long answer = 0L;
        int n = maxHeights.size();
        //制作山脉数组左侧最优解
        long[] pre = new long[n + 2];
        Deque<int[]> stack = new LinkedList<>();
        stack.push(new int[]{0, 0});
        for (int i = 0; i < n; ++i) {
            //cnt——从栈中弹出来的数字的总个数
            int h = maxHeights.get(i), cnt = 0;
            while (!stack.isEmpty() && h < stack.peek()[0]) {
                cnt += stack.pop()[1];
            }
            //maxHeights[i]入栈cnt+1个数
            stack.push(new int[]{h, cnt + 1});
            int[] p = stack.peek();
            //pre[i + 1 - p[1]]这个位置的因为没有弹出，所以其和没有变化，可以直接用，这样加起来可以得到山脉数组左侧的和
            pre[i + 1] = (long) p[0] * p[1] + pre[i + 1 - p[1]];
        }
        //如法炮制山脉数组的右边，只不过计算下标的时候要小心点
        long[] suf = new long[n + 2];
        stack = new LinkedList<>();
        stack.push(new int[]{0, 0});
        for (int i = n - 1; i >= 0; --i) {
            int h = maxHeights.get(i), cnt = 0;
            while (!stack.isEmpty() && h < stack.peek()[0]) {
                cnt += stack.pop()[1];
            }
            stack.push(new int[]{h, cnt + 1});
            int[] p = stack.peek();
            suf[i + 1] = (long) p[0] * p[1] + suf[i + 1 + p[1]];
        }
        for (int i = 0; i < n; ++i) {
            //pre[i + 1]和suf[i + 1]都包含了一个maxHeights[i]，因此需要扣除一个maxHeights[i]
            answer = Math.max(answer, pre[i + 1] + suf[i + 1] - maxHeights.get(i));
        }
        return answer;
    }

    public static void main(String[] args) {
        StackSolution solution = new StackSolution();
        Assert.isTrue(solution.canBeValid("((()(()()))()((()()))))()((()(()", "10111100100101001110100010001001"));
        Assert.isTrue(solution.canBeValid(")((())", "011011"));
        Assert.isTrue(solution.canBeValid("(((())(((())", "111111010111"));
        Assert.isTrue(solution.canBeValid("))()))", "010100"));
//        Assert.isTrue(22 == solution.maximumSumOfHeights(Arrays.asList(6,5,3,9,2,7)));
//        Assert.isTrue(13 == solution.maximumSumOfHeights(Arrays.asList(5,3,4,1,1)));
    }
}
